home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / interp / perl-5.003.tar.gz / perl-5.003.tar / perl-5.003 / x2p / hash.c < prev    next >
C/C++ Source or Header  |  1995-01-19  |  5KB  |  243 lines
  1. /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:29:20 $
  2.  *
  3.  *    Copyright (c) 1991, Larry Wall
  4.  *
  5.  *    You may distribute under the terms of either the GNU General Public
  6.  *    License or the Artistic License, as specified in the README file.
  7.  *
  8.  * $Log:    hash.c,v $
  9.  */
  10.  
  11. #include <stdio.h>
  12. #include "EXTERN.h"
  13. #include "a2p.h"
  14. #include "util.h"
  15.  
  16. STR *
  17. hfetch(tb,key)
  18. register HASH *tb;
  19. char *key;
  20. {
  21.     register char *s;
  22.     register int i;
  23.     register int hash;
  24.     register HENT *entry;
  25.  
  26.     if (!tb)
  27.     return Nullstr;
  28.     for (s=key,        i=0,    hash = 0;
  29.       /* while */ *s;
  30.      s++,        i++,    hash *= 5) {
  31.     hash += *s * coeff[i];
  32.     }
  33.     entry = tb->tbl_array[hash & tb->tbl_max];
  34.     for (; entry; entry = entry->hent_next) {
  35.     if (entry->hent_hash != hash)        /* strings can't be equal */
  36.         continue;
  37.     if (strNE(entry->hent_key,key))    /* is this it? */
  38.         continue;
  39.     return entry->hent_val;
  40.     }
  41.     return Nullstr;
  42. }
  43.  
  44. bool
  45. hstore(tb,key,val)
  46. register HASH *tb;
  47. char *key;
  48. STR *val;
  49. {
  50.     register char *s;
  51.     register int i;
  52.     register int hash;
  53.     register HENT *entry;
  54.     register HENT **oentry;
  55.  
  56.     if (!tb)
  57.     return FALSE;
  58.     for (s=key,        i=0,    hash = 0;
  59.       /* while */ *s;
  60.      s++,        i++,    hash *= 5) {
  61.     hash += *s * coeff[i];
  62.     }
  63.  
  64.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  65.     i = 1;
  66.  
  67.     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  68.     if (entry->hent_hash != hash)        /* strings can't be equal */
  69.         continue;
  70.     if (strNE(entry->hent_key,key))    /* is this it? */
  71.         continue;
  72.     /*NOSTRICT*/
  73.     Safefree(entry->hent_val);
  74.     entry->hent_val = val;
  75.     return TRUE;
  76.     }
  77.     /*NOSTRICT*/
  78.     entry = (HENT*) safemalloc(sizeof(HENT));
  79.  
  80.     entry->hent_key = savestr(key);
  81.     entry->hent_val = val;
  82.     entry->hent_hash = hash;
  83.     entry->hent_next = *oentry;
  84.     *oentry = entry;
  85.  
  86.     if (i) {                /* initial entry? */
  87.     tb->tbl_fill++;
  88.     if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  89.         hsplit(tb);
  90.     }
  91.  
  92.     return FALSE;
  93. }
  94.  
  95. #ifdef NOTUSED
  96. bool
  97. hdelete(tb,key)
  98. register HASH *tb;
  99. char *key;
  100. {
  101.     register char *s;
  102.     register int i;
  103.     register int hash;
  104.     register HENT *entry;
  105.     register HENT **oentry;
  106.  
  107.     if (!tb)
  108.     return FALSE;
  109.     for (s=key,        i=0,    hash = 0;
  110.       /* while */ *s;
  111.      s++,        i++,    hash *= 5) {
  112.     hash += *s * coeff[i];
  113.     }
  114.  
  115.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  116.     entry = *oentry;
  117.     i = 1;
  118.     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
  119.     if (entry->hent_hash != hash)        /* strings can't be equal */
  120.         continue;
  121.     if (strNE(entry->hent_key,key))    /* is this it? */
  122.         continue;
  123.     safefree((char*)entry->hent_val);
  124.     safefree(entry->hent_key);
  125.     *oentry = entry->hent_next;
  126.     safefree((char*)entry);
  127.     if (i)
  128.         tb->tbl_fill--;
  129.     return TRUE;
  130.     }
  131.     return FALSE;
  132. }
  133. #endif
  134.  
  135. void
  136. hsplit(tb)
  137. HASH *tb;
  138. {
  139.     int oldsize = tb->tbl_max + 1;
  140.     register int newsize = oldsize * 2;
  141.     register int i;
  142.     register HENT **a;
  143.     register HENT **b;
  144.     register HENT *entry;
  145.     register HENT **oentry;
  146.  
  147.     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
  148.     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
  149.     tb->tbl_max = --newsize;
  150.     tb->tbl_array = a;
  151.  
  152.     for (i=0; i<oldsize; i++,a++) {
  153.     if (!*a)                /* non-existent */
  154.         continue;
  155.     b = a+oldsize;
  156.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  157.         if ((entry->hent_hash & newsize) != i) {
  158.         *oentry = entry->hent_next;
  159.         entry->hent_next = *b;
  160.         if (!*b)
  161.             tb->tbl_fill++;
  162.         *b = entry;
  163.         continue;
  164.         }
  165.         else
  166.         oentry = &entry->hent_next;
  167.     }
  168.     if (!*a)                /* everything moved */
  169.         tb->tbl_fill--;
  170.     }
  171. }
  172.  
  173. HASH *
  174. hnew()
  175. {
  176.     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
  177.  
  178.     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
  179.     tb->tbl_fill = 0;
  180.     tb->tbl_max = 7;
  181.     hiterinit(tb);    /* so each() will start off right */
  182.     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
  183.     return tb;
  184. }
  185.  
  186. #ifdef NOTUSED
  187. hshow(tb)
  188. register HASH *tb;
  189. {
  190.     fprintf(stderr,"%5d %4d (%2d%%)\n",
  191.     tb->tbl_max+1,
  192.     tb->tbl_fill,
  193.     tb->tbl_fill * 100 / (tb->tbl_max+1));
  194. }
  195. #endif
  196.  
  197. int
  198. hiterinit(tb)
  199. register HASH *tb;
  200. {
  201.     tb->tbl_riter = -1;
  202.     tb->tbl_eiter = Null(HENT*);
  203.     return tb->tbl_fill;
  204. }
  205.  
  206. HENT *
  207. hiternext(tb)
  208. register HASH *tb;
  209. {
  210.     register HENT *entry;
  211.  
  212.     entry = tb->tbl_eiter;
  213.     do {
  214.     if (entry)
  215.         entry = entry->hent_next;
  216.     if (!entry) {
  217.         tb->tbl_riter++;
  218.         if (tb->tbl_riter > tb->tbl_max) {
  219.         tb->tbl_riter = -1;
  220.         break;
  221.         }
  222.         entry = tb->tbl_array[tb->tbl_riter];
  223.     }
  224.     } while (!entry);
  225.  
  226.     tb->tbl_eiter = entry;
  227.     return entry;
  228. }
  229.  
  230. char *
  231. hiterkey(entry)
  232. register HENT *entry;
  233. {
  234.     return entry->hent_key;
  235. }
  236.  
  237. STR *
  238. hiterval(entry)
  239. register HENT *entry;
  240. {
  241.     return entry->hent_val;
  242. }
  243.